|
The Tonelli–Shanks algorithm (referred to by Shanks as the RESSOL algorithm) is used within modular arithmetic to solve a congruence of the form : where ''n'' is a quadratic residue (mod ''p''), and ''p'' is an odd prime. Tonelli–Shanks cannot be used for composite moduli; finding square roots modulo composite numbers is a computational problem equivalent to integer factorization.〔Oded Goldreich, ''Computational complexity: a conceptual perspective'', Cambridge University Press, 2008, p. 588.〕 An equivalent, but slightly more redundant version of this algorithm was developed by Alberto Tonelli in 1891. The version discussed here was developed independently by Daniel Shanks in 1973, who explained: "My tardiness in learning of these historical references was because I had lent Volume 1 of Dickson's History to a friend and it was never returned."〔Daniel Shanks. Five Number-theoretic Algorithms. Proceedings of the Second Manitoba Conference on Numerical Mathematics. Pp. 51–70. 1973.〕 == The algorithm == (Note: All are taken to mean , unless indicated otherwise). Inputs: ''p'', an odd prime. ''n'', an integer which is a quadratic residue (mod ''p''), meaning that the Legendre symbol . Outputs: ''R'', an integer satisfying . # Factor out powers of 2 from ''p'' − 1, defining ''Q'' and ''S'' as: with ''Q'' odd. Note that if , ''i.e.'' , then solutions are given directly by . # Select a ''z'' such that the Legendre symbol (that is, ''z'' should be a quadratic non-residue modulo ''p''), and set . # Let # Loop: ## If , return ''R''. ## Otherwise, find the lowest ''i'', , such that ; ''e.g.'' via repeated squaring. ## Let , and set and . Once you have solved the congruence with ''R'' the second solution is ''p'' − ''R''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tonelli–Shanks algorithm」の詳細全文を読む スポンサード リンク
|